//30.串联所有单词的字串
#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;

vector<int> findSubstring(string s, vector<string> &words)
{
    // 定义两个哈希表用来存储字符串，建立字符串和个数之间的映射关系
    unordered_map<string, int> hashs;
    unordered_map<string, int> hashw;
    vector<int> v;

    for (auto e : words)
    {
        hashw[e]++;
    }

    int left = 0, right = 0;
    int count = 0;
    // len是words数组中每个单词的长度
    int len = words[0].size();
    int size = words[0].size();

    // pr字符串是右指针移动区间的字符串，pl字符串是左指针移动区间的字符串
    string pr;
    string pl;
    while (size--)
    {
        while (right < s.size())
        {
            // 进窗口，每次获取len长度的字符串
            pr.clear();
            while (len && len--)
            {
                pr += s[right++];
            }

            hashs[pr]++;
            len = words[0].size();

            if (hashs[pr] <= hashw[pr])
            {
                // 有效字符串的个数加一
                count++;
            }

            // 判断条件
            if ((right - left) > len * words.size())
            {
                // 左指针移动，获取len长度的字符串
                pl.clear();
                while (len && len--)
                {
                    pl += s[left++];
                }

                if (hashs[pl] <= hashw[pl])
                {
                    count--;
                }

                hashs[pl]--;
                if (hashs[pl] == 0)
                {
                    hashs.erase(pl);
                }
                len = words[0].size();
            }

            // 更新结果
            if (count == words.size())
            {
                v.push_back(left);
            }
        }
        left = right = words[0].size() - size;
        count = 0;
        hashs.clear();
    }

    return v;
}

int main()
{
    vector<string> words = {{"word"},{"good"},{"best"},{"good"}};
    string s = {"wordgoodgoodgoodbestword"};

    vector<int> v = findSubstring(s, words);
    for (auto e : v)
    {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}